package org.labuladong.动态规划算法.一维DP;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 计算最长递增子序列的长度。
 * @author Fql18
 */
public class LC_300最长递增子序列_滑动窗口 {

		public int lengthOfLIS(int[] nums) {
			// 使用列表维护当前的最长递增子序列
			List<Integer> sequence = new ArrayList<>();

			for (int num : nums) {
				// 如果列表为空或当前数字大于列表的最后一个元素，直接添加
				if (sequence.isEmpty() || num > sequence.get(sequence.size() - 1)) {
					sequence.add(num);
				} else {
					// 使用二分查找找到第一个不大于num的位置
					int index = Collections.binarySearch(sequence, num);
					if (index < 0) {
						index = -(index + 1);
					}
					// 更新找到位置的元素，因为这将导致更长的递增子序列
					sequence.set(index, num);
				}
			}

			// 返回最长递增子序列的长度
			return sequence.size();
		}

		public static void main(String[] args) {
			LC_300最长递增子序列_滑动窗口 solution = new LC_300最长递增子序列_滑动窗口();
			int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
			int length = solution.lengthOfLIS(nums);
			System.out.println(length); // 输出应该是最长递增子序列的长度
		}
}